/**
 * 给定一个左右括号字符串，以及整数K
 * 如果字符串中含有 K个左括号加K个右括号 的子串
 * 将其删除。
 * 反复删除直到不存在为止
 * 问最后的剩下的字符串
 * 
 * 向这种反复从中间删除的操作，可以使用栈来完成
 * 当场使用了伸展树，时间很大，虽然没有超时
 */
class Solution {

vector<char> Stack;
int Target;
int N;

public:
    string removeSubstring(string s, int k) {
        N = s.length();
        Target = k;
        for(int i=0;i<Target+Target-1;++i){
            Stack.push_back(s[i]);
        }
        for(int i=Target+Target-1;i<N;++i){
            Stack.push_back(s[i]);
            if(this->isok()){
                Stack.erase(Stack.end() - Target - Target, Stack.end());
            }
        }
        return string(Stack.begin(), Stack.end());
    }

    bool isok(){
        if(Stack.size() < Target + Target) return false;
        int n = Stack.size();
        for(int i=n-Target-Target;i<n-Target;++i){
            if(Stack[i]!='(')return false;
            if(Stack[i+Target]!=')') return false;
        }
        return true;
    }
};